#ifndef MTNS_H_
#define MTNS_H_

#include <algorithm>
#include <functional>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

namespace lxj
{
// 单调栈求每个位置左右两侧，离当前位置最近、且值严格小于的位置
// 给定一个可能含有重复值的数组 arr
// 找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置
// 返回所有位置相应的信息。
// 输入描述：
// 第一行输入一个数字 n，表示数组 arr 的长度。
// 以下一行输入 n 个数字，表示数组的值
// 输出描述：
// 输出n行，每行两个数字 L 和 R，如果不存在，则值为 -1，下标从 0 开始。
// 测试链接 : https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
template<class Relation,
         std::enable_if_t<std::is_same_v<std::greater<>, Relation> ||
                              std::is_same_v<std::less<>, Relation>,
                          int> = 0>
class MonoStack {
    inline constexpr static int MAXN        = 1000001;
    inline static int           stack[MAXN] = {};
    inline static int           r           = 0;

    inline void clear() { std::fill(stack, stack + MAXN, 0); }

    inline auto getType()
    {
        if constexpr (std::is_same_v<std::less<>, Relation>)
            return std::greater_equal<>();
        else
            return std::less_equal<>();
    }

    inline void compute(const std::vector<int>& arr, std::vector<std::pair<int, int>>& ans)
    {
        auto relation = this->getType();
        r             = 0;
        // 遍历阶段
        int cur;
        for (int i = 0; i < arr.size(); i++) {
            while (r > 0 && relation(arr[stack[r - 1]], arr[i])) {
                cur             = stack[--r];
                ans[cur].first  = r > 0 ? stack[r - 1] : -1;
                ans[cur].second = i;
            }
            stack[r++] = i;
        }
        // 清算阶段
        while (r > 0) {
            cur             = stack[--r];
            ans[cur].first  = r > 0 ? stack[r - 1] : -1;
            ans[cur].second = -1;
        }

        // 修正阶段
        // 左侧的答案不需要修正一定是正确的，只有右侧答案需要修正
        // 从右往左修正，n-1位置的右侧答案一定是-1，不需要修正
        for (int i = arr.size() - 2; i >= 0; i--) {
            if (ans[i].second != -1 && arr[ans[i].second] == arr[i]) {
                ans[i].second = ans[ans[i].second].second;
            }
        }
    }

public:
    inline std::vector<std::pair<int, int>> operator()(const std::vector<int>& vec)
    {
        std::vector<std::pair<int, int>> ans(vec.size());
        compute(vec, ans);
        return ans;
    }
};

// 最大宽度坡
// 给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]
// 这样的坡的宽度为 j - i，找出 A 中的坡的最大宽度，如果不存在，返回 0
// 测试链接 : https://leetcode.cn/problems/maximum-width-ramp/
inline int maxWidthRamp(std::vector<int>& nums)
{
    const int  n            = nums.size();
    static int stack[50001] = {};
    int        r            = 1;
    for (int i = 1; i < n; i++) {
        if (nums[stack[r - 1]] > nums[i]) stack[r++] = i;
    }

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (r > 0 && nums[i] >= nums[stack[r - 1]]) {
            ans = std::max(ans, i - stack[--r]);
        }
    }
    return ans;
}

// 去除重复字母保证剩余字符串的字典序最小
// 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次
// 需保证 返回结果的字典序最小
// 要求不能打乱其他字符的相对位置
// 测试链接 : https://leetcode.cn/problems/remove-duplicate-letters/
inline std::string removeDuplicateLetters(const std::string& s)
{
    static char stack[26] = {};
    static bool enter[26] = {};
    int         cnts[26]  = {};
    std::fill(enter, enter + 26, false);
    for (auto c : s) {
        cnts[c - 'a']++;
    }

    int r = 0;
    for (auto c : s) {
        if (!enter[c - 'a']) {
            while (r > 0 && stack[r - 1] > c && cnts[stack[r - 1] - 'a'] > 0) {
                enter[stack[r - 1] - 'a'] = false;
                r--;
            }
            stack[r++]     = c;
            enter[c - 'a'] = true;
        }
        cnts[c - 'a']--;
    }

    return std::string(stack, r);
}

// 大鱼吃小鱼问题
// 给定一个数组arr，每个值代表鱼的体重
// 每一轮每条鱼都会吃掉右边离自己最近比自己体重小的鱼，每条鱼向右找只吃一条
// 但是吃鱼这件事是同时发生的，也就是同一轮在A吃掉B的同时，A也可能被别的鱼吃掉
// 如果有多条鱼在当前轮找到的是同一条小鱼，那么在这一轮，这条小鱼同时被这些大鱼吃
// 请问多少轮后，鱼的数量就固定了
// 比如 : 8 3 1 5 6 7 2 4
// 第一轮 : 8吃3；3吃1；5、6、7吃2；4没有被吃。数组剩下 8 5 6 7 4
// 第二轮 : 8吃5；5、6、7吃4。数组剩下 8 6 7
// 第三轮 : 8吃6。数组剩下 8 7
// 第四轮 : 8吃7。数组剩下 8。
// 过程结束，返回4
// 测试链接 : https://www.nowcoder.com/practice/77199defc4b74b24b8ebf6244e1793de
// 测试链接 : https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
inline int totalSteps(std::vector<int>& nums)
{
    constexpr int              MAXN        = 500001;
    static std::pair<int, int> stack[MAXN] = {};
    int                        r           = 0;
    int                        ans         = 0;
    for (int i = nums.size() - 1, cur; i >= 0; i--) {
        cur = 0;
        while (r > 0 && stack[r - 1].first < nums[i]) {
            cur = std::max(stack[--r].second, cur + 1);
        }
        stack[r].first    = nums[i];
        stack[r++].second = cur;
        ans               = std::max(ans, cur);
    }
    return ans;
}

// 统计全1子矩形的数量
// 给你一个 m * n 的矩阵 mat，其中只有0和1两种值
// 请你返回有多少个 子矩形 的元素全部都是1
// 测试链接 : https://leetcode.cn/problems/count-submatrices-with-all-ones/
inline int numSubmat(std::vector<std::vector<int>>& mat)
{
    auto countFromBottom = [](std::vector<int>& heights) {
        constexpr int MAXN        = 151;
        static int    stack[MAXN] = {};
        int           r           = 0;
        int           ans         = 0;
        for (int i = 0, left, len, bottom; i < heights.size(); i++) {
            while (r > 0 && heights[stack[r - 1]] >= heights[i]) {
                int cur = stack[--r];
                if (heights[cur] > heights[i]) {
                    left   = r == 0 ? -1 : stack[r - 1];
                    len    = i - left - 1;
                    bottom = std::max(left == -1 ? 0 : heights[left], heights[i]);
                    ans += (heights[cur] - bottom) * len * (len + 1) / 2;
                }
            }
            stack[r++] = i;
        }
        while (r > 0) {
            int cur    = stack[--r];
            int left   = r == 0 ? -1 : stack[r - 1];
            int len    = heights.size() - left - 1;
            int bottom = left == -1 ? 0 : heights[left];
            ans += (heights[cur] - bottom) * len * (len + 1) / 2;
        }
        return ans;
    };

    std::vector<int> heights(mat[0].size());
    int              ans = 0;
    for (int i = 0; i < mat.size(); i++) {
        for (int j = 0; j < mat[i].size(); j++) {
            heights[j] = mat[i][j] == 0 ? 0 : heights[j] + 1;
        }
        ans += countFromBottom(heights);
    }
    return ans;
}
}   // namespace lxj

#endif